﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
// 原题连接：https://leetcode.cn/problems/find-the-distance-value-between-two-arrays/
/*
题目描述：
给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。
「距离值」 定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。

示例 1：
输入：arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
输出：2
解释：
对于 arr1[0]=4 我们有：
|4-10|=6 > d=2
|4-9|=5 > d=2
|4-1|=3 > d=2
|4-8|=4 > d=2
所以 arr1[0]=4 符合距离要求

对于 arr1[1]=5 我们有：
|5-10|=5 > d=2
|5-9|=4 > d=2
|5-1|=4 > d=2
|5-8|=3 > d=2
所以 arr1[1]=5 也符合距离要求

对于 arr1[2]=8 我们有：
|8-10|=2 <= d=2
|8-9|=1 <= d=2
|8-1|=7 > d=2
|8-8|=0 <= d=2
存在距离小于等于 2 的情况，不符合距离要求
故而只有 arr1[0]=4 和 arr1[1]=5 两个符合距离要求，距离值为 2

示例 2：
输入：arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
输出：2

示例 3：
输入：arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6
输出：1
 

提示：
1 <= arr1.length, arr2.length <= 500
-10^3 <= arr1[i], arr2[j] <= 10^3
0 <= d <= 100
*/

// 方法1——模拟
/*
思路：
按照题意进行模拟，对于arr1数组中的每一个元素arr[i]，都枚举arr2数组中的每一个元素arr2[j]，检查是否对每一个arr1[i],
都有|arr1[i] - arr2[j]| > d，如果是，则将答案answer 增加1。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int findTheDistanceValue1(int* arr1, int arr1Size, int* arr2, int arr2Size, int d) {
	assert(arr1 && arr2);
	int answer = 0;
	int i = 0;
	int j = 0;
	for (i = 0; i < arr1Size; i++) {
		for (j = 0; j < arr2Size; j++) {
			int D = arr1[i] - arr2[j] > 0 ? arr1[i] - arr2[j] : arr2[j] - arr1[i];
			if (D <= d) {
				break;
			}
		}
		if (j == arr2Size) {
			answer++;
		}
	}
	return answer;
}
// 时间复杂度：O(nm)，n和m分别为数组arr1和数组arr2的长度。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

// 方法2——二分法
/*
思路：
其实在数组arr2中寻找时，我们只需要找到第一个大于等于arr1[i]的arr2[j]和第一个小于arr1[i]的arr2[j]，
然后判断它面两个是否满足|arr1[i] - arr2[j]|，如果它们两够满足，则arr2中的所得所有元素也都满足，则将answer增加1。
而找到这两个元素正好可以在排序后用二分法进行。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
// 先写一个函数，比较两个整数的大小
int cmp_int(const void* p1, const void* p2) {
	assert(p1 && p2);
	return *((int*)p1) - *((int*)p2);
}
int findTheDistanceValue2(int* arr1, int arr1Size, int* arr2, int arr2Size, int d) {
	assert(arr1 && arr2);
	int answer = 0;
	// 先对两个数组进行排序
	qsort(arr1, arr1Size, sizeof(int), cmp_int);
	qsort(arr2, arr2Size, sizeof(int), cmp_int);
	int i = 0;
	int left = 0;
	int right = 0;
	int mid = 0;
	int D = 0;
	int flag1 = 0;
	int flag2 = 0;
	for (i = 0; i < arr1Size; i++) {
		flag1 = 0;
		flag2 = 0;
		// 先找到第一个大于等于arr1[i]的元素
		left = 0;
		right = arr2Size - 1;
		while (left < right) {
			if (arr2[left] >= arr1[i]) {
				break;
			}
			mid = left + (right - left) / 2;
			if (arr2[mid] < arr1[i]) {
				left = mid + 1;
			}
			else {
				right = mid;
			}
		}
		D = arr1[i] - arr2[left] > 0 ? arr1[i] - arr2[left] : arr2[left] - arr1[i];
		if (D > d) {
			flag1 = 1;
		}

		// 再找到第一个小于arr[i]的元素
		left = 0;
		right = arr2Size - 1;
		while (left < right) {
			if (arr2[right] < arr1[i]) {
				break;
			}
			mid = left + (right - left) / 2;
			if (arr2[mid] > arr1[i]) {
				right = mid - 1;
			}
			else {
				left = mid;
			}
		}
		D = arr1[i] - arr2[right] > 0 ? arr1[i] - arr2[right] : arr2[right] - arr1[i];
		if (D > d) {
			flag2 = 1;
		}
		if (flag1 && flag2) {
			answer++;
		}
	}
	return answer;
}

